#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if(digits.empty()){
            return result;
        }
        string path = "";
        func(digits,0,result,path);
        return result;

    }
    void func(string& digits,int i, vector<string>& result,string path){
        if(i==digits.size()){
            result.push_back(path);
            return ;
        }
        int temp;
        if(digits[i]!='7'&&digits[i]!='9'){
            temp = 3;
        }
        else{
            temp = 4;
        }
        for(int index=0;index<temp;++index){
            int t = index+(int(digits[i]-'2'))*3;
            if(digits[i]=='8'||digits[i]=='9'){
                t = t+1;
            }
            char temp = ('a'+t);
            
            func(digits,i+1,result,path+temp);
        }
    }
};

int main(){
    string digits = "9";
    Solution S;
    vector<string> result = S.letterCombinations(digits);
    return 0;
}